import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class MinPQ<Key> implements Iterable<Key> {
    /* store items at indices 1 to n*/ 
    /* its length maybe is greater than n */
    private Key[] pq;
    /* number of items on Priority Queue */
    private int n;
    /* optinal comparator */
    private Comparator<Key> comparator;

    /*
     * Initializes an empty priority queue with the given initial capacity.
     */
    public MinPQ(int initCapacity) {
        pq = (Key[]) new Object[initCapacity + 1];
        n = 0;
    }
    /* Initializes an empty priority queue */
    public MinPQ() {
        this(1);
    }

    public MinPQ(int initCapacity, Comparator<Key> comparator) {
        this.comparator = comparator;
        pq = (Key[]) new Object[initCapacity + 1];
        n = 0;
    }

    public MinPQ(Comparator<Key> comparator) {
        this(1, comparator);
    }
    /*
     * Initializes a priority queue from the array of keys.
     * Takes time proportional to the number of keys, using sink-based heap construction.
     */
    public MinPQ(Key[] keys) {
        n = keys.length;
        pq = (Key[]) new Object[n + 1];
        for(int i = 0; i < n; i++)
            pq[i+1] = keys[i];

        for(int k = n/2; k >= 1; k--)
            sink(k);

        assert isMinHeap();
    }
    public boolean isEmpty() {
        return n == 0;
    }

    public int size() {
        return n;
    }
    
    public Key min() {
        if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        return pq[1];
    }

    private void resize(int capacity) {
        assert capacity > n;
        Key[] temp = (Key[]) new Object[capacity];
        for(int i = 1; i <= n; i++) {
            temp[i] = pq[i];
        }

        pq = temp;
    }
    /* First place the key in the END of queue, and swim it */
    public void insert(Key x) {
        if(n == pq.length -1)
            resize(2 * pq.length);

        pq[++n] = x;
        swim(n);
        assert isMinHeap();
    }

    public Key delMin() {
        if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        Key min = pq[1];
        exch(1, n--);
        sink(1);
        pq[n+1] = null;
        if(n > 0 && n == (pq.length-1)/4) resize(pq.length/2);
        assert isMinHeap();
        return min;
    }

    public void testSink() {
        //exch(1, n--);
        exch(1,n);
        //sink(1);
        //pq[n+1] = null;
        //if(n > 0 && n == (pq.length-1)/4) resize(pq.length/2);
        //assert isMinHeap();
    }

    public void accUnderPQ() {
        for(int i = 1; i <= size(); i++)
            StdOut.print((String) pq[i] + " ");
    }

    private boolean isMinHeap() {
     for(int i = 1; i <= n; i++) {
         if(pq[i] == null) return false;
     }
        
     for(int i = n+1; i < pq.length; i++) {
         if(pq[i] != null) return false;
     }

     if(pq[0] != null) return false;

     return isMinHeapOrdered(1);
    }

    // Is subtree of pq[1..n] rooted at k a min heap ? 
    // recursive function
    private boolean isMinHeapOrdered(int k) {
       if(k > n) return true;
       int left = 2 * k;//left sub-node
       int right = 2 * k + 1;//right sub-node
       if(left <= n && greater(k, left)) 
           return false;
       if(right <= n && greater(k, right))
           return false;

       return isMinHeapOrdered(left) && isMinHeapOrdered(right);
    }
    /*
     *
     */

    private void swim(int k) {
        while(k > 1 && greater(k/2, k)) {
            exch(k/2,k);
            k = k/2;
        }
    }

    private void sink(int k) {
        /**/
        while(2 * k <= n) {
            int j = 2 * k;//left sub-node
            /* compare left sub-mode with right one */
            /* if left one > right one, move to right one  Anyway, choose the smaller one*/
            if(j < n && greater(j, j+1)) j++;//right sub-mode
            /* compare k with its one sub-node of two */
            if(!greater(k, j)) break;
            /* if k > its one sub-node */
            /* exchange k with its one sub-node*/
            /* eg. the bigger one move to its sub-node pos */
            exch(k, j);
            k = j;

        }
    }

    private boolean greater(int i, int j) {
        if(comparator == null) {
            return ((Comparable<Key>)pq[i]).compareTo(pq[j]) > 0;
        }
        else {
            return  comparator.compare(pq[i], pq[j]) > 0;
        }

    }

    private void exch(int i, int j) {
        Key swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
    }

    public Iterator<Key> iterator() {
        return new HeapIterator(); 
    }

    private class HeapIterator implements Iterator<Key> {

        private MinPQ<Key> copy;

        public HeapIterator() {
            if(comparator == null) 
                copy = new MinPQ<Key>(size());
            else
                copy = new MinPQ<Key>(size(), comparator);

            for(int i = 1; i <= n; i++) {
                copy.insert(pq[i]);
            }
        }

        public boolean hasNext() { return !copy.isEmpty();}
       
        public void remove() { throw new UnsupportedOperationException(); }
        public Key next() {
            if(!hasNext()) throw new NoSuchElementException();
            return copy.delMin();
        }

    }

    public static void main(String[] args) {
        MinPQ<String> pq = new MinPQ<String>();
        /* 
        while(!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if(!item.equals("-")) pq.insert(item);
            else if(!pq.isEmpty()) StdOut.print(pq.delMin() + " ");
        } */
        //StdOut.println("(" + pq.size() + " left on pq)");

        while(!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if(!item.equals("-")) pq.insert(item);
        }
        /*
        for(String s: pq) 
            StdOut.print(s + " ");
        */
        pq.accUnderPQ();
        StdOut.println();
        StdOut.println("--------------");
        pq.testSink();
        /* 
        for(String s: pq) 
            StdOut.print(s + " ");
        */
        pq.accUnderPQ();
        StdOut.println();
        

    }
    
}

